package 二叉树;

public class JZ55平衡二叉树II {

    /**
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
     * 如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
     *
     * 示例 1:
     * 给定二叉树 [3,9,20,null,null,15,7]
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回 true 。
     * 示例 2:
     * 给定二叉树 [1,2,2,3,3,null,null,4,4]
     *
     *        1
     *       / \
     *      2   2
     *     / \
     *    3   3
     *   / \
     *  4   4
     * 返回 false 。
     *
     * 限制：
     * 0 <= 树的结点个数 <= 10000
     * 注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/
     */

    /**
     * 最优解是使用后序遍历,从下往上传层数
     */

    public boolean isBalancedGood(TreeNode root) {
        return postFor(root)!=-1;
    }

    private int postFor(TreeNode node) {

        if(node==null){
            return 0;
        }

        int leftDeep = postFor(node.left);
        if(leftDeep==-1){
            return -1;
        }

        int rightDeep = postFor(node.right);
        if(rightDeep==-1){
            return -1;
        }

        //后序遍历,即最后在汇集
        return Math.abs(rightDeep-leftDeep)>1?-1:Math.max(leftDeep,rightDeep)+1;
    }

    public boolean isBalanced(TreeNode root) {

        if(root==null){
            return true;
        }

        int leftDeep = maxDeep(root.left);
        int rightDeep = maxDeep(root.right);
        if(Math.abs(leftDeep-rightDeep)>1){
            return false;
        }

//        if(root.left==null&&root.right==null){
//            return true;
//        }
//
//        if(root.left==null||root.right==null){
//            return false;
//        }

        return isBalanced(root.left)&&isBalanced(root.right);
    }

    private int maxDeep(TreeNode node) {

        if(node==null){
            return 0;
        }

        int leftMax = maxDeep(node.left);
        int rightMax = maxDeep(node.right);

        return 1+Math.max(leftMax,rightMax);
    }

    public static void main(String[] args) {
        JZ55平衡二叉树II jz=new JZ55平衡二叉树II();
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{1, 2});
        boolean result = jz.isBalanced(treeNode);
        System.out.println(result);
    }

}
